package com.gali.leetcode.day26;

import java.util.HashMap;
import java.util.Map;

/**
 * @Auther: gali
 * @Date: 2022-08-17 19:34
 * @Description:
 */
public class Solution {
     public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
    /**
     *
     * @param preorder
     * @param inorder
     * @return   从前序与中序遍历序列构造二叉树-----递归
     */
    Map<Integer, Integer> hashMap = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        for (int i = 0; i < n; i++) {
            hashMap.put(inorder[i],i);
        }
        return myBuildTree(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode myBuildTree(int[] preorder, int[] inorder, int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left>pre_right){
            return null;
        }
        //找到前序遍历根节点-----第一个节点就是根节点
        int pre_root=pre_left;
        //中序遍历的根节点
        int in_root = hashMap.get(preorder[pre_root]);
        //先把根节点建立出来
        TreeNode root = new TreeNode(preorder[pre_root]);
        //得到左子树的个数
        int tree_left=in_root-in_left;
        //递归的得到左子树的每个数
        root.left=myBuildTree(preorder,inorder,pre_left+1,pre_left+tree_left,in_left,in_root-1);
        //递归的得到右子树的每个数
        root.right=myBuildTree(preorder,inorder,pre_left+tree_left+1,pre_right,in_root+1,in_right);
        return root;
    }
}
